吴师兄学算法

# LeetCode 349、两个数组的交集

# 一、题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

# 二、题目解析

# 三、参考代码

# 方法一

哈希集合调API解法

# 题目：LC349. 两个数组的交集
# 难度：简单
# 作者：闭着眼睛学数理化
# 算法：哈希集合调API
# 代码看不懂的地方，请直接在群上提问

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

# 先将两个数组nums1和nums2用set(nums1)和set(nums2)转化为哈希集合
# 再使用两个集合的取交集操作&，得到set(nums1)和set(nums2)的交集
# 由于题目要求返回一个列表，我们还需要把交集再转化为list()，即可返回

哈希集合遍历解法

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 先获得nums1对应的哈希集合
        nums1_set = set(nums1)
        # 构建一个答案集合，初始化为空
        ans_set = set()
        
        # 遍历nums2中的元素num
        for num in nums2:
            # 如果num位于nums1对应的哈希集合nums1_set中
            if num in nums1_set:
                # 则说明num同时位于nums1和nums2中
                # 将其加入ans_set
                ans_set.add(num)
                
        # 最后将ans_set转化为列表后返回
        return (list(ans_set))

# 时空复杂度

时间复杂度：O(m+n)。nums1和nums2各自需要遍历一次。

空间复杂度：O(m+n)。两个哈希集合所占用的空间。

# 方法二*

排序+双指针解法（暂不要求掌握）

  1. # Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/intersection-of-two-arrays/
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {

        // 首先对两个数组进行排序
        Arrays.sort(nums1);

        Arrays.sort(nums2);

        // 计算出两个数组的长度
        int length1 = nums1.length ; 
        
        int length2 = nums2.length;

        // 两个数组的交集结果数组长度必然是小于等于最短数组的长度
        int[] res = new int[length1 > length2 ? length2 : length1];

        // 设置三个索引指针

        // index 指向结果数组 res ，每当 index 指向的位置填充了元素就向后移动
        int index = 0;
        
        // index1 指向数组 nums1 中的元素，将该元素和 index2 指向数组 nums2 中的元素进行比较
        int index1 = 0;
        
        // index2 指向数组 nums2 中的元素，将该元素和 index1 指向数组 nums1 中的元素进行比较
        int index2 = 0;

        // 移动 index1 和 index2 
        while (index1 < length1 && index2 < length2) {
            
            // 获取 index1 指向的元素值
            int num1 = nums1[index1];
            
            // 获取 index2 指向的元素值
            int num2 = nums2[index2];

            // num1 和 num2 的大小关系有三种

            // 1、num1 == num2
            if (num1 == num2) {

                // 由于输出结果中的每个元素一定是 【唯一】 的，所以要做一下判断
                // 如果 res 中的 index 在起始位置，说明还没有存放元素
                // 那么这个相等的元素可以存放到 res 中

                // 如果 res 中的 index 不在起始位置
                // 当它前面存放的元素并不是现在想要存放的元素
                // 那么这个相等的元素可以存放到 res 中
                if (index == 0 || num1 != res[index - 1]) {

                    // 存放到 res 中
                    res[index] = num1;
                    // 移动 index
                    index++;
                }

                // 移动 index1 ，比较其它元素
                index1++;
                // 移动 index2 ，比较其它元素
                index2++;

            // 2、num1 < num2
            } else if (num1 < num2) {
                
                // 由于两个数组已经排序了，说明此时 num1 肯定会小于 nums2 数组中 num2 后面所有的数
                // 那 num1 肯定是无法在 nums2 中找到相等的元素
                // 移动 index1 ，比较其它元素
                index1++;

            // 3、num1 > num2
            } else {

                // 由于两个数组已经排序了，说明此时 num2 肯定会小于 nums1 数组中 num1 后面所有的数
                // 那 num2 肯定是无法在 nums1 中找到相等的元素
                // 移动 index2 ，比较其它元素
                index2++;

            }
        }

        // 最后返回结果数组中有值的那些元素就行
        return Arrays.copyOfRange(res, 0, index);
    }
}

  1. # C++ 代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

        // 首先对两个数组进行排序
        sort(nums1.begin(), nums1.end());

        sort(nums2.begin(), nums2.end());
       

        // 计算出两个数组的长度
        int length1 = nums1.size();

        int length2 = nums2.size();
        
    
        // 两个数组的交集结果数组长度必然是小于等于最短数组的长度
        vector<int> res ;

        // 设置三个索引指针

        // index 指向结果数组 res ，每当 index 指向的位置填充了元素就向后移动
        // int index = 0;
        
        // index1 指向数组 nums1 中的元素，将该元素和 index2 指向数组 nums2 中的元素进行比较
        int index1 = 0;
        
        // index2 指向数组 nums2 中的元素，将该元素和 index1 指向数组 nums1 中的元素进行比较
        int index2 = 0;

        // 移动 index1 和 index2 
        while (index1 < length1 && index2 < length2) {
            
            // 获取 index1 指向的元素值
            int num1 = nums1[index1];
            
            // 获取 index2 指向的元素值
            int num2 = nums2[index2];

            // num1 和 num2 的大小关系有三种

            // 1、num1 == num2
            if (num1 == num2) {

                // 由于输出结果中的每个元素一定是 【唯一】 的，所以要做一下判断
                // 如果 res 中的 index 在起始位置，说明还没有存放元素
                // 那么这个相等的元素可以存放到 res 中

                // 如果 res 中的 index 不在起始位置
                // 当它前面存放的元素并不是现在想要存放的元素
                // 那么这个相等的元素可以存放到 res 中
                if ( !res.size() || num1 != res.back()) {

                    // 存放到 res 中
                    res.push_back(num1);
                   
                }

                // 移动 index1 ，比较其它元素
                index1++;
               
                // 移动 index2 ，比较其它元素
                index2++;

            // 2、num1 < num2
            } else if (num1 < num2) {
                
                // 由于两个数组已经排序了，说明此时 num1 肯定会小于 nums2 数组中 num2 后面所有的数
                // 那 num1 肯定是无法在 nums2 中找到相等的元素
                // 移动 index1 ，比较其它元素
                index1++;

            // 3、num1 > num2
            } else {

                // 由于两个数组已经排序了，说明此时 num2 肯定会小于 nums1 数组中 num1 后面所有的数
                // 那 num2 肯定是无法在 nums1 中找到相等的元素
                // 移动 index2 ，比较其它元素
                index2++;

            }
        }

        // 最后返回结果数组中有值的那些元素就行
        return res;

    }
};

  1. # Python 代码

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 首先对两个数组进行排序
        nums1.sort()

        nums2.sort()

        # 计算出两个数组的长度
        length1 = len(nums1)
        
        length2 = len(nums2)

        # 两个数组的交集结果数组长度必然是小于等于最短数组的长度
        res = list()

        # 设置三个索引指针

        # index 指向结果数组 res ，每当 index 指向的位置填充了元素就向后移动
        # index = 0
        
        # index1 指向数组 nums1 中的元素，将该元素和 index2 指向数组 nums2 中的元素进行比较
        index1 = 0
        
        # index2 指向数组 nums2 中的元素，将该元素和 index1 指向数组 nums1 中的元素进行比较
        index2 = 0

        # 移动 index1 和 index2 
        while index1 < length1 and index2 < length2 :
            
            # 获取 index1 指向的元素值
            num1 = nums1[index1]
            
            # 获取 index2 指向的元素值
            num2 = nums2[index2]

            # num1 和 num2 的大小关系有三种

            # 1、num1 == num2
            if num1 == num2 :

                # 由于输出结果中的每个元素一定是 【唯一】 的，所以要做一下判断
                # 如果 res 中的 index 在起始位置，说明还没有存放元素
                # 那么这个相等的元素可以存放到 res 中

                # 如果 res 中的 index 不在起始位置
                # 当它前面存放的元素并不是现在想要存放的元素
                # 那么这个相等的元素可以存放到 res 中
                if not res or num1 != res[-1]:
                    res.append(num1)

                # 移动 index1 ，比较其它元素
                index1 += 1
                # 移动 index2 ，比较其它元素
                index2 += 1

            # 2、num1 < num2
            elif num1 < num2 :
                
                # 由于两个数组已经排序了，说明此时 num1 肯定会小于 nums2 数组中 num2 后面所有的数
                # 那 num1 肯定是无法在 nums2 中找到相等的元素
                # 移动 index1 ，比较其它元素
                index1 += 1

            # 3、num1 > num2
            else:

                # 由于两个数组已经排序了，说明此时 num2 肯定会小于 nums1 数组中 num1 后面所有的数
                # 那 num2 肯定是无法在 nums1 中找到相等的元素
                # 移动 index2 ，比较其它元素
                index2 += 1

        # 最后返回结果数组中有值的那些元素就行
        return res

# 时空复杂度

时间复杂度：O(mlogm+nlogn)。两数组快排时间复杂度分别是O(mlogm)、O(nlogn)，双指针遍历需要O(m+n)，复杂度取决于较大的O(mlogm+nlogn)。

空间复杂度：O(logm+logn)。排序使用的额外空间。

← LeetCode 217、存在重复元素 →